//
// Created by 麻再挺 on 2021/1/27.
//

#include "circular_linked_list.h"

/**
 * 创建循环链表
 * @param list 链表
 * @return
 */
Status CLinked_List_Create(CLinkedList *list) {
    // 申请内存
    list = (CLinkedList *) malloc(sizeof(CLinkedList));
    // 判断是否申请成功
    if (!list) return OVERFLOW;
    // 设置头结点指向
    list->next = NULL;
    // 设置头结点数值
    list->data = 0;
    return OK;
}

/**
 * 追加数据, 在 Head 后追加
 * @param list 链表
 * @param elem 数据
 */
Status CLinked_List_Push(CLinkedList *list, ElemType elem) {
    // 赋值临时变量
    CLinkedList *p = list;
    // 获取末尾结点
    while (p->next && p->next != list) { p = p->next; }
    // 申请内存
    CLinkedList *s = (CLinkedList *) malloc(sizeof(CLinkedList));
    // 判断是否申请成功
    if (!s) return OVERFLOW;
    // 赋值数据
    s->data = elem;
    // 指向结点
    s->next = list;
    // 插入
    p->next = s;
    return OK;
}

/**
 * 插入数据
 * @param list 链表
 * @param i 索引
 * @param elem 数据
 * @return
 */
Status CLinked_List_Insert(CLinkedList *list, int i, ElemType elem) {
    // 赋值临时变量
    CLinkedList *p = list;
    // 索引
    int j = 0;
    // 查找插入位置
    while (p->next != list && j < i) {
        // 移动到下一个结点
        p = p->next;
        // 索引自增
        j++;
    }
    // 申请内存
    CLinkedList *s = (CLinkedList *) malloc(sizeof(CLinkedList));
    // 判断是否申请成功
    if (!s) return OVERFLOW;
    // 赋值数据
    s->data = elem;
    // 指向结点
    s->next = p->next;
    // 插入
    p->next = s;
    return OK;
}

/**
 * 将指向头结点的元素删除
 * @param list 列表
 * @return
 */
Status CLinked_List_Pop(CLinkedList *list) {
    // 赋值临时变量
    CLinkedList *p = list;
    // 获取末尾结点
    while (p->next->next != list) { p = p->next; }
    // 赋值链表头结点
    p->next = list;
    return OK;
}

/**
 * 删除指定索引数据
 * @param list 列表
 * @param i 索引
 * @return
 */
Status CLinked_List_Delete(CLinkedList *list, int i) {
    // 赋值临时变量
    CLinkedList *p = list;
    // 索引
    int j = 0;
    // 查找插入位置
    while (p->next != list && j < i) {
        // 移动到下一个结点
        p = p->next;
        // 索引自增
        j++;
    }
    // 结点为空, 或者当前索引大于待删除位置
    if (p->next == list) return ERROR;
    // 赋值下一个结点
    p->next = p->next->next;
    return OK;
}

/**
 * 根据索引获取链表数据
 * @param list 链表
 * @param i 索引
 * @param node 数据
 * @return
 */
Status CLinked_List_Get_Elem(CLinkedList *list, int i, CLinkedList *node) {
    // 临时链表
    CLinkedList *p = list;
    // 索引
    int j = 0;
    // 查找插入位置
    while (p->next != list && j < i) {
        // 移动到下一个结点
        p = p->next;
        // 索引自增
        j++;
    }
    // 赋值查找到的结点
    *node = *p->next;
    return OK;
}

/**
 * 合并两个线性链表, 合并后将值赋值到第一个链表中
 * @param list1 待合并线性链表
 * @param list2 待合并线性链表
 * @return
 */
Status CLinked_List_Merge(CLinkedList *list1, CLinkedList *list2) {
    // 创建临时链表
    CLinkedList *pa = list1->next, *pb = list2->next, *pc = list1;
    while (pa->next != list1 && pb->next != list2) {
        // 判断值的大小
        if (pa->data < pb->data) {
            // 赋值下一结点
            pc->next = pa;
            // 移动pc
            pc = pa;
            // 获取下一个
            pa = pa->next;
        } else {
            // 赋值下一结点
            pc->next = pb;
            // 移动pc
            pc = pb;
            // 获取下一个
            pb = pb->next;
        }
    }
    // 赋值剩余数据
//    pc->next = pa ? pa : pb;
    if (pa->next != list1) {
        // 赋值剩余数据
        pc->next = pa;
    } else {
        while (pb->next == list2) {
            // 赋值下一结点
            pc->next = pb;
            // 移动pc
            pc = pb;
            // 获取下一个
            pb = pb->next;
        }
        pb->next = list1;
    }
    return OK;
}

/**
 * 打印循环链表数据
 * @param list 链表
 */
void CLinked_List_Print(CLinkedList *list) {
    // 赋值临时变量
    CLinkedList *p = list->next;
    // 遍历打印
    while (p && list != p) {
        printf("%d\t", p->data);
        // 获取下一个结点
        p = p->next;
    }
    printf("\n");
}


